package com.wtgroup.demo.mianshi.算法.贪心;

import com.wtgroup.demo.common.util.InputParseUtil;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 《算法导论》贪心引入例题 CH16 P237
 *
 * 活动选择问题。若干场活动需要用同一个阶梯教室。每场活动有自己的开始和结束时间（[开始,结束)，左开右闭）。
 * 选取一个最大兼容集合。兼容指活动间时间不冲突，目标是尽可能多的开展活动。
 *
 * 乱序: [[3,9], [2,14], [3,5], [1,4], [12,16], [0,6], [6,10], [5,7], [8,12], [8,11], [5,9]]
 * 按结束时间升序: [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]]
 *
 * 书中已给出两个最大兼容子集:
 * [0, 3, 7, 10] , [1, 3, 8, 10].
 * [[1, 4], [5, 7], [8, 11], [12, 16]].
 *
 * 贪心策略：尽量先选择早结束的，这样剩余时间会更多，从而有更大机会在后面安排更多的活动。
 * 贪心算法的实现，就是运用人类最原始的智慧。
 * 而证明往往相当复杂，依问题不同而不同，所以一般不要纠结证明。
 *
 * 思考: 如果要求返回所有最大的兼容子集呢?
 * @author 60906
 * @date 2021/5/8 22:53
 */
public class D_活动选择 {

    static String input = "[[3,9], [2,14], [3,5], [1,4], [12,16], [0,6], [6,10], [5,7], [8,12], [8,11], [5,9]]";

    @Test
    public void testSolution_Rec() {
        List<List<Integer>> activities = InputParseUtil.parse(input);
        List<List<Integer>> res = new Solution_Rec().process(activities);
        System.out.println(res);
    }

    @Test
    public void testSolution_Iter() {
        List<List<Integer>> activities = InputParseUtil.parse(input);
        List<List<Integer>> res = new Solution_Iter().process(activities);
        System.out.println(res);
    }



    /**
     * 递归方式
     */
    class Solution_Rec {

        public List<List<Integer>> process(List<List<Integer>> activities) {
            Collections.sort(activities, (a, b) -> {
                // 按结束时间升序
                return a.get(1).compareTo(b.get(1));
            });
            System.out.println(activities);

            List<List<Integer>> vessel = new ArrayList<>();

            func(activities, 0, 0, vessel);

            return vessel;
        }

        /**
         *
         * @param activities
         * @param lastEnd 上一次的结束时间, 本次选择的活动必须至少以此为开始
         * @param start 可选择活动的自己开始位置
         * @param vessel
         * @return
         */
        private void func(List<List<Integer>> activities, int lastEnd, int start, List<List<Integer>> vessel) {
            int n = activities.size();
            // * 退出
            if (start == n) {
                return;
            }

            // * 规模缩减 k+(n+k)
            // 对于"我"而言, 我只需要取出一个可以安排的活动, 生效一坨, 交给下属干
            List<Integer> currActivity = null;
            while (start < n && (currActivity = activities.get(start)).get(0) < lastEnd ) {
                start++;
            }
            if (start < n) {
                // 有可选活动
                vessel.add(currActivity);
                func(activities, currActivity.get(1), start+1, vessel);
            }
        }
    }

    /**
     * 迭代方式
     */
    class Solution_Iter {

        public List<List<Integer>> process(List<List<Integer>> activities) {
            Collections.sort(activities, (a, b) -> {
                // 按结束时间升序
                return a.get(1).compareTo(b.get(1));
            });

            List<List<Integer>> vessel = new ArrayList<>();
            int lastEnd = 0;
            for (List<Integer> activity : activities) {
                if (activity.get(0) >= lastEnd) {
                    vessel.add(activity);
                    lastEnd = activity.get(1);
                }
            }

            return vessel;
        }

    }

    /*
    * 思考: 动态规划方式怎么实现?
    * https://www.cnblogs.com/hapjin/p/5573419.html 没看懂.
    * */

    @Test
    public void testSolution_Dp() {
        // [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]]
        int[] s = {0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, Integer.MAX_VALUE};
        int[] f = {0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16, Integer.MAX_VALUE};
        // a_0 和 a_{n+1} 特殊, 辅助用, 原 n 个活动问题转为求两者之间的最大兼容子集.
        int res = new Solution_Dp().maxCompatiableActivity(s, f, s.length - 2);
        System.out.println(res);
    }


    class Solution_Dp {
        /**
         * 算法导论中活动选择问题动态规划求解
         * https://www.cnblogs.com/hapjin/p/5573419.html 貌似第二个循环 i 下标移动方向不对, 应该自右向左.
         * https://blog.csdn.net/luoshixian099/article/details/46559737 逻辑同上, 但 i 下标是自右向左.
         *
         * 采用动态规划需要满足两个条件：1.最优子结构; 2.子问题重叠.
         * 令SijSij表示在aiai结束后和ajaj开始前活动的集合,假定AijAij为活动集合SijSij的最大兼容子集,其中包含活动akak。
         * 问题变成求SikSik与SkjSkj最大兼容活动子集AikAik与AkjAkj。我们用c[i,j]表示SijSij的最优解的大小。
         * 则c[i,j] = c[i,k]+c[k,j]+1;最后我们需要遍历所有可能的k值，找出最大的一个划分作为c[i,j]，也即有子问题重叠问题。
         * 即可以设计一个自底向上的算法，一步步到整个活动大小！
         * 算法复杂度为O(n3n3)
         * 原文链接：https://blog.csdn.net/luoshixian099/article/details/46559737
         *
         * 这里第一个活动和最后一个活动有点特殊。为了完整表示问题，构造两个虚拟的活动: a(0) 和 a(n+1)
         * 其中,s(0)=f(0)=0，s(n+1)=f(n+1)=Integer.MAX_VALUE
         * 于是，com.wtgroup.demo.面试题.我的面试.S=com.wtgroup.demo.面试题.我的面试.S(0,n+1)，从N个活动中找出最大兼容的活动，就转化成了求解 com.wtgroup.demo.面试题.我的面试.S(0,n+1)集合中包含的最多元素个数.
         * @param s 活动的开始时间
         * @param f 活动的结束时间
         * @param n 活动数目
         * @return 最大兼容的活动个数
         */
        public int maxCompatiableActivity(int[] s, int[] f, int n) {
            int[][] c = new int[n + 2][n + 2];

            /*for(int j = 0; j <= n; j++)
                for(int i = n; i >= j; i--)
                    c[i][j] = 0;//if i>=j com.wtgroup.demo.面试题.我的面试.S(i,j)是空集合*/

            int maxTemp = 0;
            for(int j = 1; j <= n+1; j++)
            {
                for(int i = j-1; i >= 0; i--)//i < j
                {
                    for(int k = i+1; k < j; k++)// i< k <j
                    {
                        if(s[k] >= f[i] && f[k] <= s[j])//com.wtgroup.demo.面试题.我的面试.S(i,j)不空
                        {
                            if(c[i][k] + c[k][j] + 1 > maxTemp)
                                maxTemp = c[i][k] + c[k][j] + 1;
                        }
                    }//inner for
                    c[i][j] = maxTemp;
                    maxTemp = 0;
                }//media for
            }//outer for
            // [0][n+1] 即表示 0~n+1 间的最大兼容子集
            return c[0][n+1];
        }
    }
}
